const tree = {
  val: 'div',
  children: [
    {
      val: 'a',
      children: [
        {
          val: 'div',
          children: []
        },
        {
          val: 'p',
          children: []
        },
        {
          val: 'a',
          children: []
        }
      ]
    },
    {
      val: 'div',
      children: [
        {
          val: 'span',
          children: []
        },
        {
          val: 'span',
          children: []
        },
        {
          val: 'p',
          children: []
        }
      ]
    }
  ]
}


const dfsTree = (root) => {
  const result = []
  const dfs = (root) => {
    if (!root) return
    result.push(root.val)
    root.children && root.children.forEach(child => {
      dfs(child)
    })
  }
  dfs(root)
  return result
}

const bfsTree = (root) => {
  const result = []
  const queue = [root]
  while (queue.length) {
    const node = queue.shift()
    if (node.val === 'p') return node
    result.push(node.val)
    node.children && node.children.forEach(child => {
      queue.push(child)
    })
  }
  return result
}
const bfslevelOrder = (root) => {
  const result = []
  if (!root) return result
  const queue = [root]
  while (queue.length) {
    const curLevel = []
    let len = queue.length
    while (len--) {
      const node = queue.shift()
      curLevel.push(node.val)
      node.children && node.children.forEach(child => {
        queue.push(child)
      })
    }
    result.push(curLevel)
  }
  return result
}


// console.log(dfsTree(tree))
// console.log(bfsTree(tree))
console.log(bfslevelOrder(tree))
// a b d e f c g h i


